package leetcode_1000;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *@author 周杨
 *describe:找出所有能够使x^i+y^j<=bound的数 
 *穷举 AC 100%
 *2019年1月12日 下午7:27:01
 */
public class PowerfulIntegers_970 {
	public List<Integer> powerfulIntegers(int x, int y, int bound) {
        List<Integer> list1 = new ArrayList<Integer>();
        List<Integer> list2 = new ArrayList<Integer>();
        Set<Integer> res = new HashSet<Integer>();
        List<Integer> t = new ArrayList<Integer>();
        int i = 1;
        if(x == 1) {
        	list1.add(1);
        }else {
	        while(i<bound) {
	        	list1.add(i);
	        	i*=x;
	        }
	        i = 1;
        }
        if(y == 1) {
        	list2.add(1);
        }else {
	        while(i<bound) {
	        	list2.add(i);
	        	i*=y;
	        }
        }
        for(int j:list1) {
        	for(int k:list2) {
        		if(j+k <= bound) {
        			res.add(j+k);
        		}else {
        			break;
        		}
        	}
        }
        for(int r:res)
        	t.add(r);
        return t;
    }
}
